package com.tgy.leetcode;

/**
 * @Author: tgy @Date: 2/4/21 9:09 AM
 *
 * 给出一个整数数组，有正有负。找到这样一个子数组，他的长度大于等于 k，且平均值最大。 保证数组的大小 >= k
 *
 * 例1:
 * 输入: [1,12,-5,-6,50,3] 3
 * 输出: 15.667
 * 解释: (-6 + 50 + 3) / 3 = 15.667
 *
 * 例2:
 * 输入: [5] 1
 * 输出: 5.000
 */
public class _643_子数组最大平均数_II {

    public static double findMaxAverage(int[] nums, int k) {

        int sum = 0;

        for (int i =0; i < k; ++i) {

            sum += nums[i];
        }
        double maxAverage = sum * 1.0 / k;

        int len = nums.length;
        for (int i = k; i < len; i++) {

            sum += nums[i];

            if (maxAverage * (i + 1) < sum) {

                maxAverage = sum * 1.0 / (i + 1);
            }

            int preSum = sum;
            for (int j = 0; j <=  i - k; j++) {

                preSum -= nums[j];
                if (maxAverage * (i - j) < preSum) {
                    maxAverage = preSum * 1.0 / (i - j);
                }
            }
        }

        return maxAverage;
    }

    public static void main(String[] args) {

        int[] nums = {1,12,-5,-6,50,3};
        int k = 3;
        double maxAverage = findMaxAverage(nums, k);
        System.out.println(maxAverage);
    }
}
